<?php
/**
 * @category Goatherd
 * @package Goatherd\Commons
 *
 * @author Copyright (c) 2012 Maik Penz <maik@phpkuh.de>
 * @version $Id: TernarySearchTrie.php 102 2012-06-08 09:05:32Z maik@phpkuh.de $
 *
 * This file is part of Goatherd library.
 *
 * Goatherd library is free software: you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * Goatherd library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with Goatherd library. If not, see <http://www.gnu.org/licenses/>.
 */
namespace Goatherd\Commons\Word;

/**
 * Generic ternary search trie implementation
 * (see http://en.wikipedia.org/wiki/Ternary_search_tries).
 *
 * Compare to http://code.google.com/p/php-ternary-search-tree/
 *
 * @package Goatherd\Commons
 * @subpackage Word
 */
class TernarySearchTrie
implements ITrie
{
    /**
     *
     * @var array
     */
    protected $_root = array(self::NODE_DATA => null);

    /**#@+
     * @var integer
     */
    const NODE_DATA = 0;
    const NODE_END_OF_WORD = 1;
    const NODE_LOW = 2;
    const NODE_EQUAL = 3;
    const NODE_HIGH = 4;
    /**#@-*/

    /**
     *
     * @var array
     */
    protected $_emptyNode = array(self::NODE_DATA => null);

    /**
     * Iterative insert.
     *
     * (non-PHPdoc)
     * @see Goatherd\Commons\Word.ITrie::add()
     */
    public function add(&$word)
    {
        $letters = $this->split($word);
        $node = &$this->_root;

        // traversing twice: letters and nodes
        foreach ($letters as $letter) {
            // walk // TODO still buggy (can not add hound on ho)
            do {
                $last = &$node;
                // extend tree
                isset($node[self::NODE_DATA])
                or $node[self::NODE_DATA] = $letter;

                // get next 'key'
                if ($node[self::NODE_DATA] > $letter) {
                    $next = self::NODE_LOW;
                } elseif ($node[self::NODE_DATA] < $letter) {
                    $next = self::NODE_HIGH;
                } else {
                    $next = self::NODE_EQUAL;
                }

                // append node if needed
                isset($node[$next]) or $node[$next] = $this->_emptyNode;
                // iterate
                $node =& $node[$next];
            } while ($next !== self::NODE_EQUAL && $last[self::NODE_DATA] !== $letter);
        }

        // mark end-of-word
        $last[self::NODE_END_OF_WORD] = true;
    }

    /**
     *
     *
     * @param array|Traversable $words
     * @throws Exception
     */
    public function addAll(&$words)
    {
        foreach ($words as &$word) {
            $this->add($word);
        }
    }

    /**
     * (non-PHPdoc)
     * @see Goatherd\Commons\Word.ITrie::has()
     */
    public function has($word)
    {
        $letters = $this->split($word);
        $last = $node = &$this->_root;
        foreach ($letters as $letter) {
            // walk lo-hi
            do {
                $last = &$node;
                // get next 'key'
                if ($node[self::NODE_DATA] > $letter) {
                    $next = self::NODE_LOW;
                } elseif ($node[self::NODE_DATA] < $letter) {
                    $next = self::NODE_HIGH;
                } else {
                    $next = self::NODE_EQUAL;
                }

                // append node if needed
                if (!isset($node[$next])) {
                    return false;
                }

                // iterate
                $node =& $node[$next];
            } while ($next !== self::NODE_EQUAL);

        }

        // test last node
        return isset($last[self::NODE_END_OF_WORD]);
    }

    /**
     * (non-PHPdoc)
     * @see Goatherd\Commons\Word.ITrie::getWords()
     */
    public function getWords()
    {
        // TODO implement
    }

    /**
     * Word-letter-conversion step.
     *
     * @param string $word
     */
    public function split(&$word)
    {
        // preg split is faster than str_split anyway (on UTF-8 data)
        return preg_split('//u', trim($word), -1, PREG_SPLIT_NO_EMPTY);
    }
}